package 剑指offer.全排列;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 输入数组 [3,32,321]
 * 输出他的全排列中，最小的数
 */
public class 第45题把数组排成最小的数 {

    /*
    最直观的方法就是全排列，同时比较排列里面的最小值。
    但是全排列在数据量大的时候会越来越慢，需要有一种新的排列方式

    从分析 [3,32,321] 入手，寻找新解法：
    上面的可以排列成：3 32 321、3 321 32、32 3 321、32 321 3、“321 32 3”、321 3 32
    但是答案却是 321 32 3

    解法核心：就是长的数字在前面，短的在后面。然后按照自然顺序排序
     */
    public static String PrintMinNumber(int[] numbers) {
        String ans = "";
        if (numbers == null || numbers.length == 0)
            return ans;
        if (numbers.length == 1)
            return String.valueOf(numbers[0]);
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.stream(numbers).forEach(list::add);
        // 排序
        list.sort((m, n) -> {
            String mn = m + "" + n;
            String nm = n + "" + m;
            return mn.compareTo(nm);
        });
        for (int s : list) {
            ans += s;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] a = {3, 32, 321};
        System.out.println(PrintMinNumber(a)); // 321323
    }
}
